/*************************************************************************************
* qTESLA: an efficient post-quantum signature scheme based on the R-LWE problem
*
* Abstract: constants for the NTT
**************************************************************************************/

#include <stdint.h>
#include "params.h"
#include "poly.h"

poly zeta ={

663045521, 592864312, 129934065, 177469925, 343322489, 76003277, 514174562, 190066344, 383213768, 787962888, 658937726, 1080673671, 1119184179, 711485619, 895353292, 741830559, 
449748398, 882352834, 210564246, 513517678, 792274530, 1106148000, 447255681, 838374925, 817124617, 494866507, 801735296, 793510817, 270693858, 301435475, 260117255, 10836133, 
1090140236, 870237322, 519619509, 74028645, 223438873, 115296996, 731671863, 711767285, 756344742, 432270821, 921367017, 743782190, 756600516, 403820997, 571909291, 809934428, 
12306094, 1080752961, 1103853276, 848006190, 651623616, 1066528111, 991262313, 90376233, 1031639319, 16581402, 195692585, 764838834, 443651394, 397689573, 855192181, 464522040, 
992536780, 1065244154, 280383996, 468397118, 363648899, 30284833, 136693103, 866826704, 684264872, 369300261, 147123393, 425272346, 947975751, 200848998, 207227922, 949139594, 
347812886, 312530409, 270384680, 1035127685, 844540200, 354908220, 399963784, 771423554, 168982346, 111911899, 891254450, 606094727, 997954525, 531583148, 617069803, 183958096, 
133356782, 708062096, 808380329, 644973028, 1122831312, 519547216, 764125907, 320659143, 557529771, 1016802360, 1043273438, 1045802164, 1034628659, 450715977, 741225144, 605149405, 
1012579499, 651882116, 904529967, 300080999, 629210435, 173034527, 989077200, 1078174711, 110168090, 256388598, 610617659, 881033840, 608872901, 50037154, 640116890, 769511414, 
738741272, 92678917, 442704510, 821794500, 142894162, 370261366, 899737750, 578322223, 983445865, 278101088, 320548969, 960437988, 847057645, 535264585, 1031091774, 384531787, 
839679409, 791760948, 937608754, 64047905, 315242491, 690211684, 304945377, 127139900, 55322681, 615105519, 1057531084, 720717234, 1061452791, 1095429367, 975341664, 483335114, 
346985754, 486624908, 954236263, 606609353, 374493515, 1026296717, 325660087, 901013385, 53959974, 212660347, 959289131, 1056916487, 1125908681, 840084518, 527647955, 143827226, 
1054554933, 861883427, 114992875, 332264810, 1071780030, 502142509, 205074888, 328230624, 728399298, 6590787, 412294778, 821072942, 186833297, 86543585, 380686974, 684478338, 
685483832, 170880254, 1049509911, 299404976, 355091877, 952129776, 345588044, 357652764, 1076734604, 924340986, 262332782, 562093746, 674846863, 869200402, 167429450, 230595565, 
379519977, 64054402, 667864494, 252591944, 174034622, 45520823, 784274107, 752467928, 436711302, 1004905853, 329220738, 721523796, 169192713, 551217408, 907929323, 194805106, 
62131815, 68055725, 545662009, 726339771, 10612113, 878659984, 675814719, 365783377, 951164276, 866711073, 684096262, 413270603, 702997992, 778608769, 127639044, 47216120, 
744109445, 430463358, 1117777586, 424051168, 656374939, 1103725866, 14621181, 919164722, 915751418, 976196867, 260519617, 802701264, 977088018, 632721351, 20944803, 435584923, 
672284530, 530447301, 1080372403, 969633414, 858453527, 467086140, 377506201, 201043187, 624606245, 356437339, 392100995, 997346375, 344147086, 1086111956, 718030456, 110621087, 
452912731, 336746546, 621211472, 795046, 794852591, 919732385, 714562897, 692647493, 521856561, 892141810, 929164476, 178245765, 949027329, 511109867, 501815810, 855826969, 
240246307, 1090455392, 871247558, 612287417, 200668298, 658636844, 62944986, 482777398, 714192478, 867140496, 199314763, 780516102, 571032048, 817693014, 607138429, 912533516, 
774019587, 835671643, 168024255, 449898784, 964159534, 486792883, 1119449268, 6657041, 86939725, 764245347, 273343215, 777897095, 930426166, 788914763, 469974947, 178163195, 
519599146, 886003889, 859825363, 1024222142, 888997684, 402918616, 146815556, 742952999, 908078470, 687435577, 647696655, 693593765, 766931890, 944985585, 394729082, 816013317, 
392951623, 65907852, 96202750, 645391372, 795224730, 402710723, 863608137, 818970673, 545310222, 970699745, 913314065, 344644471, 195858177, 414360679, 357670948, 683445481, 
833938949, 1027656845, 191164920, 78809923, 1041045426, 73270196, 101525688, 185383095, 583325181, 265134328, 467801210, 1096264575, 367433146, 474798672, 41386419, 8344607, 
170218721, 635545135, 668716283, 348890991, 155290659, 123249926, 769501318, 244415064, 1050203259, 859568787, 237251392, 995643980, 522636185, 829867059, 324850649, 618298124, 
650748178, 467147593, 524674833, 341426504, 402629779, 519829789, 805279247, 494226863, 508315225, 319600904, 48615828, 165396124, 328305874, 183239019, 878118280, 161754975, 
715041085, 746274821, 961841131, 357826469, 97008202, 885304034, 352059292, 197879468, 25678065, 1028070136, 447949253, 962673193, 813464159, 17237594, 674670906, 959137288, 
10286769, 182827874, 439769615, 875041932, 304463252, 374894049, 749497333, 38938778, 95615605, 323023572, 918611876, 207681758, 859164726, 97118122, 769881035, 360249017, 
507250246, 223795463, 24153203, 927058118, 178686381, 765072252, 491103160, 30816153, 100214484, 554568910, 715304135, 93510037, 1021905527, 1045723816, 900771572, 1011589617, 
558930760, 228903927, 41675196, 857737037, 1092385029, 1067405169, 526576034, 25638952, 1017160549, 1052660585, 364103167, 228705333, 566586884, 1126549926, 148651837, 217709216, 
614537001, 773273483, 1097591846, 480172084, 365704498, 262321659, 937989155, 1036392392, 811974084, 132591218, 799370207, 255702709, 215218285, 632314426, 58376649, 483086198, 
401012915, 839724879, 70449719, 502867571, 757507513, 1073691794, 215293647, 725537396, 398067214, 584143318, 392011063, 554158763, 730533625, 632408477, 259767996, 1124249847, 
432958856, 1026767843, 237644370, 29926518, 131813155, 898001983, 581765490, 215126607, 937229093, 1030360940, 452462053, 645808548, 645402879, 379809569, 577012489, 1082786079, 
572510912, 475330285, 152788398, 690858296, 876393456, 1002942486, 67723832, 132689262, 1030380537, 529311082, 41121650, 626066149, 866026053, 240011600, 574505003, 565608154, 
414049009, 123706126, 80739723, 326160835, 476194893, 1126100881, 646887456, 987296393, 1119394953, 994979769, 133560363, 725327130, 850262599, 132796686, 1114247361, 1040894619, 
562914322, 641645573, 817070125, 57537779, 59054681, 878878988, 307674440, 1001013577, 594860688, 879718195, 318482613, 698792051, 756144110, 204900318, 1031928100, 926221256, 
695955308, 662601363, 408725276, 424272249, 110402404, 535365123, 226700293, 372920839, 1118626221, 1070521569, 639548808, 621533107, 260391977, 316354318, 362523650, 733090366, 
456807669, 113808372, 399369653, 647539514, 165899708, 312376469, 213806296, 208149196, 937880087, 289692684, 580756218, 963782721, 1086045881, 705999228, 1115084349, 508210869, 
893248141, 1109740411, 338975294, 752813515, 622466015, 372202503, 55041759, 338412385, 29530795, 689413481, 974303137, 605274799, 812143197, 121492617, 758223932, 200993249, 
575018581, 1039577172, 1090395670, 612284976, 414561447, 886969, 685649488, 667914411, 183143190, 272811635, 104938162, 64626548, 404300448, 333824065, 399917080, 105374124, 
329534966, 930231830, 187994078, 772453163, 81595362, 135380677, 536704334, 787124497, 554875178, 60344266, 790999625, 581578940, 72453408, 872892444, 204321645, 885844343, 
942736233, 12824064, 23018086, 996569940, 818486394, 1484060, 349940348, 981882207, 855621323, 1034617940, 565456643, 745822751, 68273335, 578729865, 170455086, 173683666, 
375983003, 128070235, 982298151, 650454518, 218561113, 1063878953, 541912322, 695738038, 232263685, 671557037, 584280432, 126161631, 394804150, 149748923, 670383088, 150214459, 
409907258, 730673023, 452696559, 556617060, 271416278, 398913344, 793695740, 603610724, 620753264, 760650912, 867673149, 32169440, 106515963, 802984660, 859117007, 854436840, 
736728629, 789197380, 1065424969, 689713946, 980964818, 605711034, 1105012640, 552261321, 980118632, 868407647, 247404352, 182421983, 1076188005, 324001412, 258504546, 973008126, 
458306267, 216381363, 1099063604, 172774993, 897006405, 662034826, 827348922, 213283635, 712936407, 586286121, 133326382, 771279651, 77080161, 692598228, 272139235, 156805228, 
184634865, 216660729, 331306952, 180435518, 1098019508, 642364354, 759605128, 444205747, 818119290, 697748488, 779633860, 1123069299, 628905992, 1093632915, 363341708, 896455329, 
653929021, 348858884, 483831705, 248783457, 50018777, 527261991, 1108955766, 683741144, 838366046, 1040212608, 956504693, 441862460, 181267978, 415765896, 551409278, 866054366, 
855141207, 141967451, 462022373, 903388714, 5583486, 624006881, 1027131584, 127103419, 227496735, 876597209, 1075725589, 13097576, 275925041, 46896293, 1047922947, 480370214, 
979242782, 304620097, 88645237, 157252101, 1080960020, 1019514352, 910182857, 344499049, 841029348, 586201316, 561562804, 877577189, 774682172, 420802584, 243335866, 818233882, 
1102088786, 910997938, 394459347, 114606856, 959148981, 304978043, 15246639, 410347623, 819777499, 304889937, 196333903, 294201539, 742724283, 136229739, 1095082129, 710673795, 
303958022, 730529672, 330937766, 290549001, 975944911, 1012630530, 940739802, 428357654, 876150675, 270868991, 605451019, 692162505, 164423625, 414486664, 567335281, 60501334, 
301815246, 988181982, 749960008, 971794624, 1044979874, 846257184, 944403720, 1028849636, 20676966, 402436874, 1038249855, 636703483, 52612884, 457266419, 404964279, 764097082, 
73543501, 850137726, 543909567, 478253061, 341753973, 145701153, 816141937, 150699764, 1012159718, 996158125, 874816245, 140152812, 1046568846, 731360631, 165696325, 923351799, 
373705673, 295885033, 571437494, 323580072, 535312031, 261690954, 128330254, 678037418, 730169337, 800223155, 493938662, 1035925088, 1086213401, 1029948847, 703929623, 1067237691, 
203498545, 260171642, 489884813, 595714326, 717921496, 379455421, 739695761, 991791615, 1101866478, 768413486, 248059075, 641256446, 252045193, 383431807, 1098526663, 655518597, 
868514850, 975851412, 607928997, 1015436331, 219860723, 248644475, 1100013490, 1059262194, 616750819, 706912112, 186194896, 371412253, 932777950, 605371544, 32806481, 41915372, 
942949174, 657520226, 337575994, 767026353, 795340494, 602216057, 1051603235, 38167611, 383256063, 961974657, 643676937, 850900578, 1033468109, 791020067, 602254362, 742154500, 
5280825, 557072845, 260014823, 274231000, 957875719, 620840911, 468091423, 844999033, 1097180885, 635575570, 741694428, 564249983, 1015743243, 179096376, 326642449, 737067396, 
404230544, 164870855, 233971733, 25568965, 480191729, 304346683, 43284571, 600295394, 805273167, 1081440213, 132076275, 660273218, 115344223, 436181422, 581442439, 521590088, 
278258022, 1016124223, 326820478, 833856285, 578613123, 981790341, 912622887, 677878660, 983305736, 582146018, 50261960, 421861087, 688852042, 1053015424, 638857404, 13988561, 
613374169, 246804474, 354822706, 755945338, 48594230, 1112837032, 490266853, 331336539, 573470525, 482415512, 1066189384, 480749813, 340470541, 1087888528, 866254054, 328905420, 
282987588, 772186429, 280721545, 827109021, 1065603359, 319039186, 632282960, 368180744, 103743324, 1039700039, 944775691, 35416271, 876336840, 387995308, 744351857, 1024873450, 
846245765, 488549456, 793960147, 360822038, 1047746824, 70006457, 1081240530, 845224049, 158270603, 1040065115, 109153922, 842769347, 357450022, 745529551, 127101430, 1013053569, 
653900906, 1066692138, 1026185333, 40127076, 888550251, 1074046165, 859190733, 172044729, 232991700, 856026028, 181368869, 11312168, 965826001, 718641942, 140897415, 300107020, 
760832029, 454871649, 538869148, 209839945, 603404196, 1070516093, 362685617, 594598150, 706680144, 248566695, 624350428, 687354425, 108825926, 996763990, 768570600, 192652503, 
1030980703, 285993613, 678456384, 666912839, 636939881, 724986064, 567331335, 1109690969, 786490830, 1041275289, 13569330, 310803565, 1018122073, 236560398, 625689685, 227532759, 
773302523, 275485190, 151580837, 1097590370, 43338286, 709601963, 530263051, 696952520, 591327015, 779208675, 900380693, 779322099, 365008051, 816626432, 9177437, 715814813, 
951132001, 978726879, 539618044, 330049876, 794850808, 75659606, 535871088, 1117571277, 1035668574, 737539534, 638053030, 1067376479, 817653745, 608323193, 952285144, 489088626, 
643974231, 1100308604, 80188084, 1009055308, 528621558, 845717932, 574893980, 185963698, 304405106, 254075674, 885653667, 125272317, 310803515, 431578311, 49069840, 734649900, 
64565269, 68004786, 877673289, 927546004, 379372125, 179774076, 313581255, 48547291, 669540902, 805507558, 458763285, 808407028, 467495228, 200042934, 286655832, 204624339, 
1076184783, 580415818, 422842319, 130214533, 1019327141, 196299734, 544501682, 1039357725, 139924087, 1079672537, 517801387, 1103773407, 832398676, 971715180, 249998343, 17982966, 
226812113, 1056456541, 429118671, 1115368643, 731996995, 114969826, 90081103, 503306049, 601600644, 221645888, 419902454, 366845662, 668188540, 595203705, 289744999, 311876332, 
708499030, 814702169, 1038171811, 305413430, 1025269191, 401153805, 524933941, 244137773, 690611117, 1006016675, 368084114, 695256047, 400388115, 315582560, 240063473, 316625045, 
193016450, 444532677, 490320790, 1007751505, 809310640, 335632874, 932973140, 879894932, 664689650, 582802605, 524248338, 381467584, 15568620, 102853205, 344510143, 244997234, 
228087680, 804700227, 33671368, 202173391, 810352194, 941527027, 107007723, 250295846, 439491161, 385750316, 881611329, 305721499, 489662560, 253590441, 574217985, 187749275, 
767834897, 577560416, 666585061, 536277466, 31104595, 459368906, 738728273, 395846485, 915511988, 152055976, 123475832, 434555954, 708682317, 873350950, 733405860, 594180445, 
508539260, 411702537, 525230789, 245498406, 807139759, 421829267, 576175978, 671688378, 586113326, 717964200, 549178465, 340455344, 177498005, 185915353, 758077402, 35174925, 
62477885, 432126554, 865525725, 94991243, 953163796, 64489669, 63466463, 1027121609, 603180773, 102927367, 328204523, 849484682, 1106252192, 166218129, 336284946, 115841434, 
394987097, 1071354740, 1124188058, 756569276, 1109657140, 693362574, 582653179, 356054504, 10684879, 43556307, 683161419, 43248060, 311516690, 801263962, 259313122, 1076460000, 
627348913, 723691023, 1029014449, 1100617454, 910402911, 804049172, 439314326, 277694586, 89508968, 45373766, 191679221, 573131182, 602365665, 620254956, 594424107, 763083130, 
984103431, 746523686, 419387264, 1030279302, 774892955, 242854266, 102748733, 633218020, 205014651, 835462852, 458575555, 34062189, 765679808, 999547926, 509921953, 785947219, 
966902522, 639941920, 244960006, 581685840, 1052422889, 674992133, 61665140, 451012255, 122965849, 190085617, 748838858, 349331162, 529980624, 16193587, 34516478, 42504381, 
160246364, 173535194, 187379517, 111011381, 365394663, 102220644, 699473271, 366177836, 81692890, 659930501, 36322222, 896361190, 473670263, 1039987458, 412734344, 864218684, 
138309539, 146538307, 1101721292, 898028054, 727055521, 601140835, 577133426, 451632863, 725601236, 388561051, 696130927, 299179408, 194132814, 104549843, 919472671, 900644523, 
848766532, 557407329, 506005527, 529295823, 637231568, 840578154, 40752048, 1043021730, 940132528, 1635875, 390473136, 36409813, 938731454, 1005273567, 169556667, 456362115, 
968015234, 385125443, 1033592386, 622268544, 824710397, 811874465, 1126356395, 1030647864, 1027801728, 1032615842, 990780079, 340414618, 431920306, 797512392, 36624143, 1039964580, 
78368304, 725419125, 1031876274, 545277986, 400681087, 824700406, 916868477, 979226643, 327065594, 666022464, 692190875, 241031536, 486380927, 271722557, 903843361, 141586809, 
747887461, 634534510, 613428929, 35052951, 519999706, 907994356, 122720932, 47771789, 111045658, 101409844, 478385667, 160271513, 709331396, 407803014, 233222181, 446853856, 
325464420, 902760210, 272094082, 341360162, 749117421, 560701701, 963877946, 787641615, 205947725, 590645393, 232274153, 623635766, 912309623, 1120569701, 620395638, 104547179, 
326785462, 462547537, 940416330, 25839620, 19867751, 37744827, 852776583, 515439522, 254321646, 368159144, 977334258, 457474804, 545693728, 590432747, 485742318, 929078943, 
737942351, 275516935, 808617222, 720700675, 172457394, 549776288, 773237950, 425343903, 106571968, 735846275, 60428193, 122914286, 749764808, 987165321, 38777778, 78068884, 
255797430, 533180457, 948660956, 48180746, 1126178511, 529625145, 556629751, 638195644, 832146389, 336969603, 525037491, 33022927, 179961503, 1111138669, 8606225, 744603862, 
831709431, 936738778, 976276214, 628380488, 186998645, 1058798754, 681993880, 653924606, 946881757, 648359538, 739466740, 91286181, 294298084, 874448181, 197552840, 1095208028, 
1044083721, 391228026, 525623627, 1098872860, 195023028, 787479821, 623295468, 953049875, 598245883, 53206653, 107774100, 1118437046, 444804586, 736921099, 245341091, 386750976, 
133313309, 679691423, 1106023536, 311728621, 298633293, 401684808, 243635798, 110079800, 995741344, 323549381, 934619946, 561564543, 318482785, 437414717, 954436048, 120567824, 
939556676, 96791826, 457592630, 938550164, 338458435, 235369986, 520146590, 367137669, 215447981, 816673608, 388257556, 367337840, 505745620, 16797457, 625598745, 670629880, 
254936589, 910270385, 42251434, 163010455, 35446687, 313308255, 882198755, 1020005685, 629715947, 45305629, 160442570, 751826615, 839359276, 665790727, 1126866480, 206409968, 
243347643, 601811321, 987009162, 748255207, 204576339, 60528047, 215906665, 956509919, 298034351, 23754044, 490568798, 458549410, 38365707, 66017494, 289322020, 23546127, 
1110422453, 430589196, 451259509, 452129088, 246026906, 479959331, 657705765, 154141097, 545145366, 756619911, 1056054068, 305614614, 982437349, 733683110, 356219317, 138617825, 
1077109241, 367006768, 107952142, 792745355, 1101149620, 190430549, 642564451, 1027811321, 529836063, 856677079, 136144741, 193585315, 759745460, 929992250, 670307004, 1127656802, 
1006741766, 845736365, 936834519, 1017230852, 281391123, 580173947, 30327752, 1121201269, 1055919747, 182909919, 160816233, 602222114, 380162230, 868238592, 238843489, 626593576, 
827265325, 474165116, 237320246, 663594943, 436318864, 1049025048, 70720879, 971089740, 88817691, 635640003, 121885571, 243941023, 2431313, 941718254, 799204753, 612476838, 
941429841, 218425031, 62583588, 843195067, 826107237, 360474616, 699278259, 879607149, 103065937, 68048433, 88684453, 368247280, 352557675, 958077844, 188716852, 142753212, 
187289952, 1075600752, 538047877, 79021856, 72991411, 855788038, 872392901, 230685283, 684292160, 1006193052, 389933214, 858196548, 879451470, 275454910, 233947442, 798039506, 
522351014, 1028810225, 973496946, 459028464, 716757179, 299354781, 303032004, 378782749, 726394798, 822245773, 1112315820, 572181708, 792445736, 354854796, 391571531, 1120313604, 
948219264, 683224878, 109721560, 210780537, 877361416, 837335205, 829228039, 710692263, 336548681, 1113948080, 500533488, 561629043, 1004877220, 538880595, 121199664, 933983782, 
1012189335, 466644222, 948695748, 1030237630, 409196123, 831874921, 209931563, 472212875, 667493959, 374083498, 121993645, 135468879, 743372774, 445381601, 1056162737, 535313411, 
731504361, 106330271, 449811720, 1025526021, 538706550, 384586636, 672759140, 214035474, 1061388936, 1083928033, 581161697, 343521559, 467089784, 918062822, 197840310, 276992034, 
267922106, 626045501, 689381922, 1031751565, 453082931, 703374420, 543907459, 1101013667, 158907990, 531648771, 96624556, 1107736421, 653786417, 1020275778, 1100295652, 1080331394, 
934499233, 1103133235, 665774139, 760309263, 583529543, 927074230, 109488746, 759686422, 658349346, 1121943871, 528665116, 800822916, 210288486, 526666123, 265162098, 797138998, 
225170105, 773601444, 1074231036, 358050025, 792486275, 559918288, 931510368, 283561253, 929909084, 643871325, 165045098, 236482168, 27010690, 947252425, 762156229, 403915775, 
226420583, 111771291, 457403715, 390913388, 417791477, 1051596236, 218412938, 231310973, 913814997, 1010678562, 1061436357, 402561769, 46161499, 194906871, 1106996555, 1044025883, 
84769121, 958130074, 458164325, 75716319, 742943036, 662710618, 1015724782, 541305935, 887985887, 374173602, 667853276, 1118405527, 888897413, 806335907, 483810195, 94681964, 
932049061, 419630532, 863884216, 258267823, 871542447, 748276380, 1089602035, 956286084, 452661681, 297101315, 292838603, 602202013, 59322052, 868600049, 695946675, 1119453722, 
369279180, 571163895, 1076824823, 613633165, 1105924843, 970753160, 38059756, 230436803, 993075206, 825136859, 772252886, 665426090, 252341082, 81169114, 15411109, 1109435384, 
169742336, 879343295, 637603710, 1050610062, 543393828, 360888011, 622980636, 538625088, 384365656, 954674344, 672395534, 822045489, 271453575, 379517678, 745140555, 64423305, 
132805764, 730783710, 818513567, 1062263522, 633828399, 609441394, 952235218, 443525262, 408766329, 154648340, 321016488, 39971097, 975003097, 115001826, 929799112, 1079586908, 
630403891, 883673758, 1017692831, 982184607, 1052333730, 732655912, 673402471, 144580658, 776541469, 599807837, 897876410, 750409126, 408883399, 800706291, 525848844, 1043397101, 
546417436, 927622216, 923472422, 126273770, 976796416, 301390002, 640312848, 64953087, 850801014, 80099312, 344764299, 166353727, 304339056, 563820482, 620610256, 95176064, 
436429135, 450761768, 1080607344, 554114394, 1051016002, 1094965858, 1044316801, 90082309, 802170370, 785939405, 96092255, 481999812, 399399466, 798786453, 1069910963, 1075397160, 
645632403, 721614722, 81169724, 16732546, 256145620, 1032181185, 858152279, 261506136, 939613769, 1109259166, 1072545109, 893701664, 1076290454, 94376212, 1129486743, 496007349, 
461211004, 215869774, 903345586, 185658758, 769007243, 973105742, 843449005, 531620573, 115498344, 118893063, 1080559132, 289993254, 729094212, 100228973, 970141524, 88018590, 
401752692, 490667846, 120206196, 1053373040, 927137503, 109156130, 1099960359, 852051778, 542020710, 890761046, 935484975, 503476669, 247175418, 137646228, 122463313, 1098625172, 
313612773, 1045687932, 942418016, 223296002, 613265129, 618070459, 210263615, 258537008, 687201993, 1069972265, 1092070505, 209044958, 705866604, 959480062, 37107231, 530334549, 
940857114, 888162459, 550603427, 833686010, 914377969, 777858517, 823074720, 257780639, 682005406, 79684712, 1108405948, 546085914, 695245394, 296369184, 90008780, 876596576, 
1060844810, 971909901, 180162302, 155422312, 913147941, 572392352, 172449506, 707256652, 379461286, 396142844, 341990080, 626969834, 156354367, 614031487, 682424885, 1092771510, 
881893810, 1087158911, 85380176, 1044830162, 986021749, 619772632, 829678380, 1095084953, 726141659, 941134286, 949047185, 1013348374, 17076281, 979953556, 730262704, 692286875, 
723405610, 879517616, 639675138, 319980056, 711102461, 564387868, 1089317723, 659400607, 372246588, 1035423048, 766956675, 186444638, 504211183, 871579167, 64189114, 905789437, 
};
poly zetainv ={

1065536839, 258146786, 625514770, 943281315, 362769278, 94302905, 757479365, 470325346, 40408230, 565338085, 418623492, 809745897, 490050815, 250208337, 406320343, 437439078, 
399463249, 149772397, 1112649672, 116377579, 180678768, 188591667, 403584294, 34641000, 300047573, 509953321, 143704204, 84895791, 1044345777, 42567042, 247832143, 36954443, 
447301068, 515694466, 973371586, 502756119, 787735873, 733583109, 750264667, 422469301, 957276447, 557333601, 216578012, 974303641, 949563651, 157816052, 68881143, 253129377, 
1039717173, 833356769, 434480559, 583640039, 21320005, 1050041241, 447720547, 871945314, 306651233, 351867436, 215347984, 296039943, 579122526, 241563494, 188868839, 599391404, 
1092618722, 170245891, 423859349, 920680995, 37655448, 59753688, 442523960, 871188945, 919462338, 511655494, 516460824, 906429951, 187307937, 84038021, 816113180, 31100781, 
1007262640, 992079725, 882550535, 626249284, 194240978, 238964907, 587705243, 277674175, 29765594, 1020569823, 202588450, 76352913, 1009519757, 639058107, 727973261, 1041707363, 
159584429, 1029496980, 400631741, 839732699, 49166821, 1010832890, 1014227609, 598105380, 286276948, 156620211, 360718710, 944067195, 226380367, 913856179, 668514949, 633718604, 
239210, 1035349741, 53435499, 236024289, 57180844, 20466787, 190112184, 868219817, 271573674, 97544768, 873580333, 1112993407, 1048556229, 408111231, 484093550, 54328793, 
59814990, 330939500, 730326487, 647726141, 1033633698, 343786548, 327555583, 1039643644, 85409152, 34760095, 78709951, 575611559, 49118609, 678964185, 693296818, 1034549889, 
509115697, 565905471, 825386897, 963372226, 784961654, 1049626641, 278924939, 1064772866, 489413105, 828335951, 152929537, 1003452183, 206253531, 202103737, 583308517, 86328852, 
603877109, 329019662, 720842554, 379316827, 231849543, 529918116, 353184484, 985145295, 456323482, 397070041, 77392223, 147541346, 112033122, 246052195, 499322062, 50139045, 
199926841, 1014724127, 154722856, 1089754856, 808709465, 975077613, 720959624, 686200691, 177490735, 520284559, 495897554, 67462431, 311212386, 398942243, 996920189, 1065302648, 
384585398, 750208275, 858272378, 307680464, 457330419, 175051609, 745360297, 591100865, 506745317, 768837942, 586332125, 79115891, 492122243, 250382658, 959983617, 20290569, 
1114314844, 1048556839, 877384871, 464299863, 357473067, 304589094, 136650747, 899289150, 1091666197, 158972793, 23801110, 516092788, 52901130, 558562058, 760446773, 10272231, 
433779278, 261125904, 1070403901, 527523940, 836887350, 832624638, 677064272, 173439869, 40123918, 381449573, 258183506, 871458130, 265841737, 710095421, 197676892, 1035043989, 
645915758, 323390046, 240828540, 11320426, 461872677, 755552351, 241740066, 588420018, 114001171, 467015335, 386782917, 1054009634, 671561628, 171595879, 1044956832, 85700070, 
22729398, 934819082, 1083564454, 727164184, 68289596, 119047391, 215910956, 898414980, 911313015, 78129717, 711934476, 738812565, 672322238, 1017954662, 903305370, 725810178, 
367569724, 182473528, 1102715263, 893243785, 964680855, 485854628, 199816869, 846164700, 198215585, 569807665, 337239678, 771675928, 55494917, 356124509, 904555848, 332586955, 
864563855, 603059830, 919437467, 328903037, 601060837, 7782082, 471376607, 370039531, 1020237207, 202651723, 546196410, 369416690, 463951814, 26592718, 195226720, 49394559, 
29430301, 109450175, 475939536, 21989532, 1033101397, 598077182, 970817963, 28712286, 585818494, 426351533, 676643022, 97974388, 440344031, 503680452, 861803847, 852733919, 
931885643, 211663131, 662636169, 786204394, 548564256, 45797920, 68337017, 915690479, 456966813, 745139317, 591019403, 104199932, 679914233, 1023395682, 398221592, 594412542, 
73563216, 684344352, 386353179, 994257074, 1007732308, 755642455, 462231994, 657513078, 919794390, 297851032, 720529830, 99488323, 181030205, 663081731, 117536618, 195742171, 
1008526289, 590845358, 124848733, 568096910, 629192465, 15777873, 793177272, 419033690, 300497914, 292390748, 252364537, 918945416, 1020004393, 446501075, 181506689, 9412349, 
738154422, 774871157, 337280217, 557544245, 17410133, 307480180, 403331155, 750943204, 826693949, 830371172, 412968774, 670697489, 156229007, 100915728, 607374939, 331686447, 
895778511, 854271043, 250274483, 271529405, 739792739, 123532901, 445433793, 899040670, 257333052, 273937915, 1056734542, 1050704097, 591678076, 54125201, 942436001, 986972741, 
941009101, 171648109, 777168278, 761478673, 1041041500, 1061677520, 1026660016, 250118804, 430447694, 769251337, 303618716, 286530886, 1067142365, 911300922, 188296112, 517249115, 
330521200, 188007699, 1127294640, 885784930, 1007840382, 494085950, 1040908262, 158636213, 1059005074, 80700905, 693407089, 466131010, 892405707, 655560837, 302460628, 503132377, 
890882464, 261487361, 749563723, 527503839, 968909720, 946816034, 73806206, 8524684, 1099398201, 549552006, 848334830, 112495101, 192891434, 283989588, 122984187, 2069151, 
459418949, 199733703, 369980493, 936140638, 993581212, 273048874, 599889890, 101914632, 487161502, 939295404, 28576333, 336980598, 1021773811, 762719185, 52616712, 991108128, 
773506636, 396042843, 147288604, 824111339, 73671885, 373106042, 584580587, 975584856, 472020188, 649766622, 883699047, 677596865, 678466444, 699136757, 19303500, 1106179826, 
840403933, 1063708459, 1091360246, 671176543, 639157155, 1105971909, 831691602, 173216034, 913819288, 1069197906, 925149614, 381470746, 142716791, 527914632, 886378310, 923315985, 
2859473, 463935226, 290366677, 377899338, 969283383, 1084420324, 500010006, 109720268, 247527198, 816417698, 1094279266, 966715498, 1087474519, 219455568, 874789364, 459096073, 
504127208, 1112928496, 623980333, 762388113, 741468397, 313052345, 914277972, 762588284, 609579363, 894355967, 791267518, 191175789, 672133323, 1032934127, 190169277, 1009158129, 
175289905, 692311236, 811243168, 568161410, 195106007, 806176572, 133984609, 1019646153, 886090155, 728041145, 831092660, 817997332, 23702417, 450034530, 996412644, 742974977, 
884384862, 392804854, 684921367, 11288907, 1021951853, 1076519300, 531480070, 176676078, 506430485, 342246132, 934702925, 30853093, 604102326, 738497927, 85642232, 34517925, 
932173113, 255277772, 835427869, 1038439772, 390259213, 481366415, 182844196, 475801347, 447732073, 70927199, 942727308, 501345465, 153449739, 192987175, 298016522, 385122091, 
1121119728, 18587284, 949764450, 1096703026, 604688462, 792756350, 297579564, 491530309, 573096202, 600100808, 3547442, 1081545207, 181064997, 596545496, 873928523, 1051657069, 
1090948175, 142560632, 379961145, 1006811667, 1069297760, 393879678, 1023153985, 704382050, 356488003, 579949665, 957268559, 409025278, 321108731, 854209018, 391783602, 200647010, 
643983635, 539293206, 584032225, 672251149, 152391695, 761566809, 875404307, 614286431, 276949370, 1091981126, 1109858202, 1103886333, 189309623, 667178416, 802940491, 1025178774, 
509330315, 9156252, 217416330, 506090187, 897451800, 539080560, 923778228, 342084338, 165848007, 569024252, 380608532, 788365791, 857631871, 226965743, 804261533, 682872097, 
896503772, 721922939, 420394557, 969454440, 651340286, 1028316109, 1018680295, 1081954164, 1007005021, 221731597, 609726247, 1094673002, 516297024, 495191443, 381838492, 988139144, 
225882592, 858003396, 643345026, 888694417, 437535078, 463703489, 802660359, 150499310, 212857476, 305025547, 729044866, 584447967, 97849679, 404306828, 1051357649, 89761373, 
1093101810, 332213561, 697805647, 789311335, 138945874, 97110111, 101924225, 99078089, 3369558, 317851488, 305015556, 507457409, 96133567, 744600510, 161710719, 673363838, 
960169286, 124452386, 190994499, 1093316140, 739252817, 1128090078, 189593425, 86704223, 1088973905, 289147799, 492494385, 600430130, 623720426, 572318624, 280959421, 229081430, 
210253282, 1025176110, 935593139, 830546545, 433595026, 741164902, 404124717, 678093090, 552592527, 528585118, 402670432, 231697899, 28004661, 983187646, 991416414, 265507269, 
716991609, 89738495, 656055690, 233364763, 1093403731, 469795452, 1048033063, 763548117, 430252682, 1027505309, 764331290, 1018714572, 942346436, 956190759, 969479589, 1087221572, 
1095209475, 1113532366, 599745329, 780394791, 380887095, 939640336, 1006760104, 678713698, 1068060813, 454733820, 77303064, 548040113, 884765947, 489784033, 162823431, 343778734, 
619804000, 130178027, 364046145, 1095663764, 671150398, 294263101, 924711302, 496507933, 1026977220, 886871687, 354832998, 99446651, 710338689, 383202267, 145622522, 366642823, 
535301846, 509470997, 527360288, 556594771, 938046732, 1084352187, 1040216985, 852031367, 690411627, 325676781, 219323042, 29108499, 100711504, 406034930, 502377040, 53265953, 
870412831, 328461991, 818209263, 1086477893, 446564534, 1086169646, 1119041074, 773671449, 547072774, 436363379, 20068813, 373156677, 5537895, 58371213, 734738856, 1013884519, 
793441007, 963507824, 23473761, 280241271, 801521430, 1026798586, 526545180, 102604344, 1066259490, 1065236284, 176562157, 1034734710, 264200228, 697599399, 1067248068, 1094551028, 
371648551, 943810600, 952227948, 789270609, 580547488, 411761753, 543612627, 458037575, 553549975, 707896686, 322586194, 884227547, 604495164, 718023416, 621186693, 535545508, 
396320093, 256375003, 421043636, 695169999, 1006250121, 977669977, 214213965, 733879468, 390997680, 670357047, 1098621358, 593448487, 463140892, 552165537, 361891056, 941976678, 
555507968, 876135512, 640063393, 824004454, 248114624, 743975637, 690234792, 879430107, 1022718230, 188198926, 319373759, 927552562, 1096054585, 325025726, 901638273, 884728719, 
785215810, 1026872748, 1114157333, 748258369, 605477615, 546923348, 465036303, 249831021, 196752813, 794093079, 320415313, 121974448, 639405163, 685193276, 936709503, 813100908, 
889662480, 814143393, 729337838, 434469906, 761641839, 123709278, 439114836, 885588180, 604792012, 728572148, 104456762, 824312523, 91554142, 315023784, 421226923, 817849621, 
839980954, 534522248, 461537413, 762880291, 709823499, 908080065, 528125309, 626419904, 1039644850, 1014756127, 397728958, 14357310, 700607282, 73269412, 902913840, 1111742987, 
879727610, 158010773, 297327277, 25952546, 611924566, 50053416, 989801866, 90368228, 585224271, 933426219, 110398812, 999511420, 706883634, 549310135, 53541170, 925101614, 
843070121, 929683019, 662230725, 321318925, 670962668, 324218395, 460185051, 1081178662, 816144698, 949951877, 750353828, 202179949, 252052664, 1061721167, 1065160684, 395076053, 
1080656113, 698147642, 818922438, 1004453636, 244072286, 875650279, 825320847, 943762255, 554831973, 284008021, 601104395, 120670645, 1049537869, 29417349, 485751722, 640637327, 
177440809, 521402760, 312072208, 62349474, 491672923, 392186419, 94057379, 12154676, 593854865, 1054066347, 334875145, 799676077, 590107909, 150999074, 178593952, 413911140, 
1120548516, 313099521, 764717902, 350403854, 229345260, 350517278, 538398938, 432773433, 599462902, 420123990, 1086387667, 32135583, 978145116, 854240763, 356423430, 902193194, 
504036268, 893165555, 111603880, 818922388, 1116156623, 88450664, 343235123, 20034984, 562394618, 404739889, 492786072, 462813114, 451269569, 843732340, 98745250, 937073450, 
361155353, 132961963, 1020900027, 442371528, 505375525, 881159258, 423045809, 535127803, 767040336, 59209860, 526321757, 919886008, 590856805, 674854304, 368893924, 829618933, 
988828538, 411084011, 163899952, 1118413785, 948357084, 273699925, 896734253, 957681224, 270535220, 55679788, 241175702, 1089598877, 103540620, 63033815, 475825047, 116672384, 
1002624523, 384196402, 772275931, 286956606, 1020572031, 89660838, 971455350, 284501904, 48485423, 1059719496, 81979129, 768903915, 335765806, 641176497, 283480188, 104852503, 
385374096, 741730645, 253389113, 1094309682, 184950262, 90025914, 1025982629, 761545209, 497442993, 810686767, 64122594, 302616932, 849004408, 357539524, 846738365, 800820533, 
263471899, 41837425, 789255412, 648976140, 63536569, 647310441, 556255428, 798389414, 639459100, 16888921, 1081131723, 373780615, 774903247, 882921479, 516351784, 1115737392, 
490868549, 76710529, 440873911, 707864866, 1079463993, 547579935, 146420217, 451847293, 217103066, 147935612, 551112830, 295869668, 802905475, 113601730, 851467931, 608135865, 
548283514, 693544531, 1014381730, 469452735, 997649678, 48285740, 324452786, 529430559, 1086441382, 825379270, 649534224, 1104156988, 895754220, 964855098, 725495409, 392658557, 
803083504, 950629577, 113982710, 565475970, 388031525, 494150383, 32545068, 284726920, 661634530, 508885042, 171850234, 855494953, 869711130, 572653108, 1124445128, 387571453, 
527471591, 338705886, 96257844, 278825375, 486049016, 167751296, 746469890, 1091558342, 78122718, 527509896, 334385459, 362699600, 792149959, 472205727, 186776779, 1087810581, 
1096919472, 524354409, 196948003, 758313700, 943531057, 422813841, 512975134, 70463759, 29712463, 881081478, 909865230, 114289622, 521796956, 153874541, 261211103, 474207356, 
31199290, 746294146, 877680760, 488469507, 881666878, 361312467, 27859475, 137934338, 390030192, 750270532, 411804457, 534011627, 639841140, 869554311, 926227408, 62488262, 
425796330, 99777106, 43512552, 93800865, 635787291, 329502798, 399556616, 451688535, 1001395699, 868034999, 594413922, 806145881, 558288459, 833840920, 756020280, 206374154, 
964029628, 398365322, 83157107, 989573141, 254909708, 133567828, 117566235, 979026189, 313584016, 984024800, 787971980, 651472892, 585816386, 279588227, 1056182452, 365628871, 
724761674, 672459534, 1077113069, 493022470, 91476098, 727289079, 1109048987, 100876317, 185322233, 283468769, 84746079, 157931329, 379765945, 141543971, 827910707, 1069224619, 
562390672, 715239289, 965302328, 437563448, 524274934, 858856962, 253575278, 701368299, 188986151, 117095423, 153781042, 839176952, 798788187, 399196281, 825767931, 419052158, 
34643824, 993496214, 387001670, 835524414, 933392050, 824836016, 309948454, 719378330, 1114479314, 824747910, 170576972, 1015119097, 735266606, 218728015, 27637167, 311492071, 
886390087, 708923369, 355043781, 252148764, 568163149, 543524637, 288696605, 785226904, 219543096, 110211601, 48765933, 972473852, 1041080716, 825105856, 150483171, 649355739, 
81803006, 1082829660, 853800912, 1116628377, 54000364, 253128744, 902229218, 1002622534, 102594369, 505719072, 1124142467, 226337239, 667703580, 987758502, 274584746, 263671587, 
578316675, 713960057, 948457975, 687863493, 173221260, 89513345, 291359907, 445984809, 20770187, 602463962, 1079707176, 880942496, 645894248, 780867069, 475796932, 233270624, 
766384245, 36093038, 500819961, 6656654, 350092093, 431977465, 311606663, 685520206, 370120825, 487361599, 31706445, 949290435, 798419001, 913065224, 945091088, 972920725, 
857586718, 437127725, 1052645792, 358446302, 996399571, 543439832, 416789546, 916442318, 302377031, 467691127, 232719548, 956950960, 30662349, 913344590, 671419686, 156717827, 
871221407, 805724541, 53537948, 947303970, 882321601, 261318306, 149607321, 577464632, 24713313, 524014919, 148761135, 440012007, 64300984, 340528573, 392997324, 275289113, 
270608946, 326741293, 1023209990, 1097556513, 262052804, 369075041, 508972689, 526115229, 336030213, 730812609, 858309675, 573108893, 677029394, 399052930, 719818695, 979511494, 
459342865, 979977030, 734921803, 1003564322, 545445521, 458168916, 897462268, 433987915, 587813631, 65847000, 911164840, 479271435, 147427802, 1001655718, 753742950, 956042287, 
959270867, 550996088, 1061452618, 383903202, 564269310, 95108013, 274104630, 147843746, 779785605, 1128241893, 311239559, 133156013, 1106707867, 1116901889, 186989720, 243881610, 
925404308, 256833509, 1057272545, 548147013, 338726328, 1069381687, 574850775, 342601456, 593021619, 994345276, 1048130591, 357272790, 941731875, 199494123, 800190987, 1024351829, 
729808873, 795901888, 725425505, 1065099405, 1024787791, 856914318, 946582763, 461811542, 444076465, 1128838984, 715164506, 517440977, 39330283, 90148781, 554707372, 928732704, 
371502021, 1008233336, 317582756, 524451154, 155422816, 440312472, 1100195158, 791313568, 1074684194, 757523450, 507259938, 376912438, 790750659, 19985542, 236477812, 621515084, 
14641604, 423726725, 43680072, 165943232, 548969735, 840033269, 191845866, 921576757, 915919657, 817349484, 963826245, 482186439, 730356300, 1015917581, 672918284, 396635587, 
767202303, 813371635, 869333976, 508192846, 490177145, 59204384, 11099732, 756805114, 903025660, 594360830, 1019323549, 705453704, 721000677, 467124590, 433770645, 203504697, 
97797853, 924825635, 373581843, 430933902, 811243340, 250007758, 534865265, 128712376, 822051513, 250846965, 1070671272, 1072188174, 312655828, 488080380, 566811631, 88831334, 
15478592, 996929267, 279463354, 404398823, 996165590, 134746184, 10331000, 142429560, 482838497, 3625072, 653531060, 803565118, 1048986230, 1006019827, 715676944, 564117799, 
555220950, 889714353, 263699900, 503659804, 1088604303, 600414871, 99345416, 997036691, 1062002121, 126783467, 253332497, 438867657, 976937555, 654395668, 557215041, 46939874, 
552713464, 749916384, 484323074, 483917405, 677263900, 99365013, 192496860, 914599346, 547960463, 231723970, 997912798, 1099799435, 892081583, 102958110, 696767097, 5476106, 
869957957, 497317476, 399192328, 575567190, 737714890, 545582635, 731658739, 404188557, 914432306, 56034159, 372218440, 626858382, 1059276234, 290001074, 728713038, 646639755, 
1071349304, 497411527, 914507668, 874023244, 330355746, 997134735, 317751869, 93333561, 191736798, 867404294, 764021455, 649553869, 32134107, 356452470, 515188952, 912016737, 
981074116, 3176027, 563139069, 901020620, 765622786, 77065368, 112565404, 1104087001, 603149919, 62320784, 37340924, 271988916, 1088050757, 900822026, 570795193, 118136336, 
228954381, 84002137, 107820426, 1036215916, 414421818, 575157043, 1029511469, 1098909800, 638622793, 364653701, 951039572, 202667835, 1105572750, 905930490, 622475707, 769476936, 
359844918, 1032607831, 270561227, 922044195, 211114077, 806702381, 1034110348, 1090787175, 380228620, 754831904, 825262701, 254684021, 689956338, 946898079, 1119439184, 170588665, 
455055047, 1112488359, 316261794, 167052760, 681776700, 101655817, 1104047888, 931846485, 777666661, 244421919, 1032717751, 771899484, 167884822, 383451132, 414684868, 967970978, 
251607673, 946486934, 801420079, 964329829, 1081110125, 810125049, 621410728, 635499090, 324446706, 609896164, 727096174, 788299449, 605051120, 662578360, 478977775, 511427829, 
804875304, 299858894, 607089768, 134081973, 892474561, 270157166, 79522694, 885310889, 360224635, 1006476027, 974435294, 780834962, 461009670, 494180818, 959507232, 1121381346, 
1088339534, 654927281, 762292807, 33461378, 661924743, 864591625, 546400772, 944342858, 1028200265, 1056455757, 88680527, 1050916030, 938561033, 102069108, 295787004, 446280472, 
772055005, 715365274, 933867776, 785081482, 216411888, 159026208, 584415731, 310755280, 266117816, 727015230, 334501223, 484334581, 1033523203, 1063818101, 736774330, 313712636, 
734996871, 184740368, 362794063, 436132188, 482029298, 442290376, 221647483, 386772954, 982910397, 726807337, 240728269, 105503811, 269900590, 243722064, 610126807, 951562758, 
659751006, 340811190, 199299787, 351828858, 856382738, 365480606, 1042786228, 1123068912, 10276685, 642933070, 165566419, 679827169, 961701698, 294054310, 355706366, 217192437, 
522587524, 312032939, 558693905, 349209851, 930411190, 262585457, 415533475, 646948555, 1066780967, 471089109, 929057655, 517438536, 258478395, 39270561, 889479646, 273898984, 
627910143, 618616086, 180698624, 951480188, 200561477, 237584143, 607869392, 437078460, 415163056, 209993568, 334873362, 1128930907, 508514481, 792979407, 676813222, 1019104866, 
411695497, 43613997, 785578867, 132379578, 737624958, 773288614, 505119708, 928682766, 752219752, 662639813, 271272426, 160092539, 49353550, 599278652, 457441423, 694141030, 
1108781150, 497004602, 152637935, 327024689, 869206336, 153529086, 213974535, 210561231, 1115104772, 26000087, 473351014, 705674785, 11948367, 699262595, 385616508, 1082509833, 
1002086909, 351117184, 426727961, 716455350, 445629691, 263014880, 178561677, 763942576, 453911234, 251065969, 1119113840, 403386182, 584063944, 1061670228, 1067594138, 934920847, 
221796630, 578508545, 960533240, 408202157, 800505215, 124820100, 693014651, 377258025, 345451846, 1084205130, 955691331, 877134009, 461861459, 1065671551, 750205976, 899130388, 
962296503, 260525551, 454879090, 567632207, 867393171, 205384967, 52991349, 772073189, 784137909, 177596177, 774634076, 830320977, 80216042, 958845699, 444242121, 445247615, 
749038979, 1043182368, 942892656, 308653011, 717431175, 1123135166, 401326655, 801495329, 924651065, 627583444, 57945923, 797461143, 1014733078, 267842526, 75171020, 985898727, 
602077998, 289641435, 3817272, 72809466, 170436822, 917065606, 1075765979, 228712568, 804065866, 103429236, 755232438, 523116600, 175489690, 643101045, 782740199, 646390839, 
154384289, 34296586, 68273162, 409008719, 72194869, 514620434, 1074403272, 1002586053, 824780576, 439514269, 814483462, 1065678048, 192117199, 337965005, 290046544, 745194166, 
98634179, 594461368, 282668308, 169287965, 809176984, 851624865, 146280088, 551403730, 229988203, 759464587, 986831791, 307931453, 687021443, 1037047036, 390984681, 360214539, 
489609063, 1079688799, 520853052, 248692113, 519108294, 873337355, 1019557863, 51551242, 140648753, 956691426, 500515518, 829644954, 225195986, 477843837, 117146454, 524576548, 
388500809, 679009976, 95097294, 83923789, 86452515, 112923593, 572196182, 809066810, 365600046, 610178737, 6894641, 484752925, 321345624, 421663857, 996369171, 945767857, 
512656150, 598142805, 131771428, 523631226, 238471503, 1017814054, 960743607, 358302399, 729762169, 774817733, 285185753, 94598268, 859341273, 817195544, 781913067, 180586359, 
922498031, 928876955, 181750202, 704453607, 982602560, 760425692, 445461081, 262899249, 993032850, 1099441120, 766077054, 661328835, 849341957, 64481799, 137189173, 665203913, 
274533772, 732036380, 686074559, 364887119, 934033368, 1113144551, 98086634, 1039349720, 138463640, 63197842, 478102337, 281719763, 25872677, 48972992, 1117419859, 319791525, 
557816662, 725904956, 373125437, 385943763, 208358936, 697455132, 373381211, 417958668, 398054090, 1014428957, 906287080, 1055697308, 610106444, 259488631, 39585717, 1118889820, 
869608698, 828290478, 859032095, 336215136, 327990657, 634859446, 312601336, 291351028, 682470272, 23577953, 337451423, 616208275, 919161707, 247373119, 679977555, 387895394, 
234372661, 418240334, 10541774, 49052282, 470788227, 341763065, 746512185, 939659609, 615551391, 1053722676, 786403464, 952256028, 999791888, 536861641, 466680432, 223936516, 
};

